人生第一次被T组数卡了
A B
签到
C
被T组数卡了，每次是最少1e4的复杂度，搞1e5个1就把我ban了啊
直接考虑每个数，别每次遍历到1e4即可
D
用错误的算法并查集瞎搞，没考虑到环的情况
正解
自己做题不懂脑子活该错啊1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
using namespace std;
const int maxn=2e5+5,MD=1e9+7,INF=0x3f3f3f3f;
int vis[maxn], p[maxn], n, a[maxn], c[maxn];
int dfs(int x,int mark)
{
if(vis[x]) return INF;
int ans=INF;
vis[x]=mark;
int v=a[x];
if(!vis[v])
ans=min(ans, dfs(v, mark));
else if(vis[v]==mark) {
ans=c[x];
for(int i=v; i!=x; i=a[i])
ans=min(ans, c[i]);
}
return ans;
}
int main()
{
scanf("%d", &n);
for(int i=1;i<=n;i++)
scanf("%d", &c[i]);
for(int i=1;i<=n;i++)
scanf("%d", &a[i]);
int ans=0;
for(int i=1;i<=n;i++){
if(!vis[i]) {
int now = dfs(i, i+1);
if(now != INF) {
ans += now;
}
}
}
printf("%d\n", ans);
return 0;
}